package leetcode

//https://leetcode.com/problems/median-of-two-sorted-arrays/
/**
 * 由于限定时间复杂度为log(m+n)，所以只有二分查找可以做到
 * 同时数组是有序的，所以这里可以使用二分的思想。传统的二分查找是在一个有序的
 * 是组中不断进行二分 找到某个值的位置，而这里需要对k进行二分
 * 因为给定的是两个有序的数组，我们可以先对两个数组 二分 如果a[k/2] = nums2[k/2]那么肯定 中位数就是a[k/2]
 * 如果a[k/2]< nums2[k/2] 那么 nums1[0~ k/2]区间的数字必然 是第0~k之间的数字 ，那么接下来去 nums1[k/2+1 ~ m] 和b里面寻找
 * 知道最后划分的区间只有一个元素为止
 */
//1 2 3 4 5 6 8//11 15 16 17 18 19 20
val nums1 = intArrayOf(1, 2)
val nums2 = intArrayOf(3, 4)
fun main(args: Array<String>) {
    val k = (nums1.size + nums2.size + 1) / 2
    val kRightClose = (nums1.size + nums2.size + 2) / 2
//
//    var nTh = findNth(nums1, nums2, k)
//    var nPlus = findNth(nums1, nums2, kRightClose)
//    println("$nTh  $nPlus")
//    println((nTh + nPlus) / 2f)

    //非递归实现
    println(findNthNonRecursive(nums1, nums2, k))
    println(findNthNonRecursive(nums1, nums2, kRightClose))

}

fun findNth(a: IntArray, b: IntArray, k: Int): Int {
    val m = a.size
    val n = a.size
    if (m > n)
        return findNth(a, b, k)
    if (m == 0)
        return b[k - 1]
    if (k == 1)
        return Math.min(a[0], b[0])

    var p = Math.min(k / 2, m)//由于m<n,所以需要判断是否可能越界
    var L = a[p - 1]
    var R = b[k - p - 1] //如果不再a的 0~p 范围内，那么就在b的 0~ k-p范围内

    if (L < R)//nums1 左边0~p的元素可以被抛弃
        return findNth(a.copyOfRange(p, a.size), b, k - p)
    //b左边k-p个元素可以抛弃，继续在剩下的元素里面寻找第p大元素
    else return findNth(a, b.copyOfRange(k - p, b.size), p)

}

//非递归实现
fun findNthNonRecursive(a: IntArray, b: IntArray, k: Int): Int {

    var m = if (a.size < b.size) a else b
    var n = if (m === a) b else a
    var kTh = k
    var mSp = 0 //m start position
    var mEp = m.size - 1  //m end position
    var nSp = 0
    var nEp = n.size - 1
    while (mEp - mSp >= 0 && nEp - nSp >= 0 && kTh != 1) {//因为结束下标是包含的，所以终止条件是不满足 >=0 即 <0 此时起始下标已经越过终止下标
        val p = Math.min(kTh / 2, mEp - mSp + 1)//compare k/2 and the length of  sort.getArray m
        val q = kTh - p
        val L = m[p + mSp - 1]
        val R = n[nSp + q - 1]
        if (L < R) {
            mSp += p
            nEp = nSp + q - 1
            kTh -= p
        } else {
            mEp = mSp + p - 1
            nSp += q
            kTh -= q
        }

    }

    if (mEp - mSp < 0)
        return n[nSp + kTh - 1]
    if (nEp - nSp < 0)
        return m[mSp + kTh - 1]
    if (kTh == 1)
        return Math.min(m[mSp], n[nSp])

    //this will not happen
    throw IllegalStateException("Cannot find the median of these two sorted arrays")

}